package A_review.review6_30;

import binaryTree.basic.TreeNode;

public class MergeSort {

    //如何进行前序遍历
    public  void   preTraverse(TreeNode  root){
        if (root==null){
            return;
        }
        System.out.println(root.val);
        preTraverse(root.left);
        preTraverse(root.right);
    }

    public  void   inTraverse(TreeNode  root){
        if (root==null){
            return;
        }
       inTraverse(root.left);
        System.out.println(root.val);
        inTraverse(root.right);
    }

    public  void   postTraverse(TreeNode  root){
        if (root==null){
            return;
        }
        postTraverse(root.left);
        postTraverse(root.right);
        System.out.println(root.val);
    }

//归并排序就是后序遍历
int count=0;
        public  int mergeSort(int[] nums){
            int length = nums.length;
            int lo=0;
            int hi=length-1;
            int[] temp=new int[length];
            sort(nums,lo,hi,temp);
            return  count;
    }


    public  void  sort(int[] nums,int lo,int hi,int[] temp){
        if (lo>=hi){
            return;
        }
        int mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        merge(nums,lo,mid,hi,temp);
    }


    public  void  merge(int[] nums,int lo,int mid,int hi,int[] temp){
     int j=lo;
     int k=mid+1;
     int i=0;
     while (j<=mid&&k<=hi){
         if (nums[j]<=nums[k]){
             temp[i++]=nums[j++];
         }
         else {
             //TODO:2023/7/23  点睛之笔  厉害
             count+=(mid+1)-j;
             temp[i++]=nums[k++];
         }
     }

     while (j<=mid){
         temp[i++]=nums[j++];
     }

     while (k<=hi){
           temp[i++]=nums[k++];
     }


        for(int t=0;t<i;t++){
            nums[lo+t] = temp[t];
        }


    }


    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[]  arr={1,3,2,3,1};

        System.out.println(mergeSort.mergeSort(arr));
        for (int a: arr
        ) {
            System.out.println(a);

        }

    }







}
